Data sorting is a process where starting with "N" random elements, an order is created such that E.sub.1 &lt;E.sub.2 &lt;E.sub.3 &lt;. . . E.sub.N known as ascending order, or, also E.sub.N &gt;E.sub.N-1 &gt;E.sub.N-2 &gt;. . . E.sub.1 known as descending order. The elements can be ordered numerically or logically.
It is desired that the data sorting process be as fast as possible and, to that end, a number of algorithms have been implemented. Some machines process each element one at a time and a significant speed increase can be achieved if many elements can be manipulated concurrently. In general, all "N" elements are not available simultaneously and it is, therefore, desirable to start processing the elements as soon as these become available.
It is desirable that the sorting apparatus or engine has pipelining, concurrency, utilize the host's memory, and has a comparator count that does not limit the sorting capacity. Pipelining is the ability to accept and supply data--continuously one unit of data per fastest machine cycle. Concurrency (sometimes also referred to as parallelism or chaining) is the processing of two or more arithmetic/logical operations at a time. Usually, in order to achieve concurrency, a plurality of dedicated memory modules is used. This, in turn, is costly in terms of product cost, package bulk, power consumption and, above all, limits the sort capacity to that of the dedicated memory. It is therefore highly desirable that the sorting apparatus utilize the host's memory. Many sorting apparatus or engines call for a plurality of comparators. Such count is sometimes tied to a particular quantity such as "C" where a multiple of "C" becomes the maximum number of the elements that can be sorted. It is desirable to provide an apparatus where there is no limit on the sort capacity even with a few comparators. In the prior art such as in U.S. Pat. No. 4,520,456 of Miranker et al entitled "Dual Reciprocating Pipelined Sorter", U.S. Pat. No. 4,131,947 of Armstrong et al entitled "Random Access Digital Sorter", and the U.S. Pat. No. 4,595,995 of Alles entitled "Sort Circuit and Method Using Multiple Parallel Sorts of the Sorted Items," all of these sorting apparatus require a dedicated memory and have a number of comparators where such count determines the maximum number of the elements that can be sorted. U.S. Pat. No. 4,559,612 of Vrielink entitled "Sorting Device for Data Words" is pipelined input, not pipelined as to output, has dedicated memorv and is very memory intensive. In the U.S. Pat. No. 4,567,572 of Morris et al entitled "Fast Parallel Sorting Processor", the comparator count does not limit the sorting capacity, but this patent has dedicated memory, the pipelining has delay and is software controlled and believed relatively slow. U.S. Pat. No. 4,210,961 describes a software process for sorting. European Patent Application No. 0149,213 of Hitachi, Ltd. filed Dec. 21, 1984 entitled "Vector Processor" is pipelined, utilizes Host's memory, has no limit on sorting capacity, but is not concurrent. It has a constant convergence toward sort completion, regardless of the data content, that is in proportion to N*Log(N).
This invention, for random input (source) data, converges toward completion in proportion to N*Log(N)/Log(S) where `S` is the number of stages and having a minimum of two stages. Also, when source data is sorted and contains some random elements as is the case when updating an existing sorted file, the concurrent sorting engine converges toward completion in proportion to N. All logarithms are base 2.